/*方法一：前缀和 + 哈希表
朴素的思路是遍历数组 nums 的每个大小至少为 2 的子数组并计算每个子数组的元素和，判断是否存在一个子数组的元素和为 k 的倍数。当数组 nums 的长度为 m 时，上述思路需要用 O(m 
2
 ) 的时间遍历全部子数组，对于每个子数组需要 O(m) 的时间计算元素和，因此时间复杂度是 O(m 
3
 )，会超出时间限制，因此必须优化。

如果事先计算出数组 nums 的前缀和数组，则对于任意一个子数组，都可以在 O(1) 的时间内得到其元素和。用 prefixSums[i] 表示数组 nums 从下标 0 到下标 i 的前缀和，则 nums 从下标 p+1 到下标 q（其中 p<q）的子数组的长度为 q−p，该子数组的元素和为 prefixSums[q]−prefixSums[p]。

如果 prefixSums[q]−prefixSums[p] 为 k 的倍数，且 q−p≥2，则上述子数组即满足大小至少为 2 且元素和为 k 的倍数。

当 prefixSums[q]−prefixSums[p] 为 k 的倍数时，prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同。因此只需要计算每个下标对应的前缀和除以 k 的余数即可，使用哈希表存储每个余数第一次出现的下标。

规定空的前缀的结束下标为 −1，由于空的前缀的元素和为 0，因此在哈希表中存入键值对 (0,−1)。对于 0≤i<m，从小到大依次遍历每个 i，计算每个下标对应的前缀和除以 k 的余数，并维护哈希表：

如果当前余数在哈希表中已经存在，则取出该余数在哈希表中对应的下标 prevIndex，nums 从下标 prevIndex+1 到下标 i 的子数组的长度为 i−prevIndex，该子数组的元素和为 k 的倍数，如果 i−prevIndex≥2，则找到了一个大小至少为 2 且元素和为 k 的倍数的子数组，返回 true；

如果当前余数在哈希表中不存在，则将当前余数和当前下标 i 的键值对存入哈希表中。

由于哈希表存储的是每个余数第一次出现的下标，因此当遇到重复的余数时，根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足元素和为 k 的倍数的子数组长度中的最大值。只要最大长度至少为 2，即存在符合要求的子数组。
*/
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> firstRemainderIndex; // 记录余数第一次出现的下标
        int prefixSum = 0;
        firstRemainderIndex[prefixSum % k] = -1;
        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            int remainder = prefixSum % k;
            if (firstRemainderIndex.find(remainder) != firstRemainderIndex.end()) {
                if (i - firstRemainderIndex[remainder] >= 2) {
                    return true;
                }
            } else {
                firstRemainderIndex[remainder] = i;
            }
        }
        return false;
    }
};